//动态规划
//维护一个数组prev_sum记录前缀和
//一边更新prev_sum一边记录前面前缀和的最小值prev_min
//子数组的和 = 末尾位置的前缀和 - 起始位置的前缀和
//这样就可以通过（新的前缀和 - prev_min）得到子数组和，并更新结果
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int ret = nums[0], prev_min = nums[0] > 0 ? 0 : nums[0];
        vector<int> prev_sum(len, nums[0]);

        for (int i = 1; i < len; i++)
        {
            prev_sum[i] = prev_sum[i - 1] + nums[i];
            ret = max(ret, prev_sum[i] - prev_min);
            prev_min = min(prev_min, prev_sum[i]);
        }

        return ret;
    }
};